package main

import (
	"fmt"
	"math/rand"
	"time"
)

func selectMax(arr []int) int {
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
	}
	return max
}
func bitSort(arr []int, bit int) (ret []int) {
	length := len(arr)
	bitcounts := make([]int, 10)
	for i := 0; i < length; i++ {
		num := (arr[i] / bit) % 10
		bitcounts[num]++
	}
	for i := 1; i < 10; i++ {
		bitcounts[i] += bitcounts[i-1]
	}
	ret = make([]int, length)
	for i := length - 1; i >= 0; i-- {
		num := (arr[i] / bit) % 10
		ret[bitcounts[num]-1] = arr[i]
		bitcounts[num]--
	}
	return
}
func radixSort(arr []int) []int {
	max := selectMax(arr)
	for bit := 1; max/bit > 0; bit *= 10 {
		arr = bitSort(arr, bit)
		fmt.Println(arr)
	}
	return arr
}

func main() {
	arr:=make([]int,100)
	rand.Seed(time.Now().UnixNano())

	length:=len(arr)
	for i := 0; i < length; i++ {
		arr[i]=rand.Intn(1000)
	}
	fmt.Println(arr)
	fmt.Println(radixSort(arr))
}
